package com.example.demo.leetcode100题;

import com.example.demo.StopWatchTemplate;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author：zzc
 * @date: 2022/9/4
 */
public class 二叉树的前序遍历 {

    //输入：root = [1,null,2,3]
    //输出：[1,2,3]
    //示例 2：
    //输入：root = []
    //输出：[]
    //示例 3：
    //输入：root = [1]
    //输出：[1]

    // 中 左 右
    public static void main(String[] args) {

        System.out.println(StopWatchTemplate.doSupplier(() -> qianxubianli2(new TreeNode())));
    }

    private static List<Integer> qianxubianli2(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack  = new LinkedList<>();

        while (root != null ||!stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }

    private static List<Integer> qianxubianli(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        assessNode(root, res);
        return res;
    }

    private static void assessNode(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        assessNode(root.left, res);
        assessNode(root.right, res);
    }


}
